#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll calc(int a,int b)
{
    if(a==b)
        return 0;
    return 1ll*a*b/__gcd(a,b);
}
int main()
{
    freopen("never.in","r",stdin);
    freopen("never.out","w",stdout);
    int q;
    scanf("%d",&q);
    while(q--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        ll ans=min(calc(a,2)+calc(2,b),calc(a,b));
        if(__gcd(a,b)>1)
            ans=min(ans,0ll+a+b);
        int minn1=a,minn2=b;
        for(int i=2;i<=4000;i++)
        {
            if(!(a%i))
                minn1=min(minn1,i);
            if(!(b%i))
                minn2=min(minn2,i);
        }
        ans=min(ans,min(min(calc(a,minn1)+calc(minn1,minn2)+calc(minn2,b),calc(a,minn1)+calc(minn1,2)+calc(2,minn2)+calc(minn2,b)),min(calc(a,minn1)+calc(minn1,2)+calc(2,b),calc(a,2)+calc(2,minn2)+calc(minn2,b))));
        printf("%lld\n",ans);
    }
    return 0;
}